A gain graph is a

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...

whose edges are labelled "invertibly", or "orientably", by elements of a

group A group is a number of persons or things that are located, gathered, or classed together. Groups of people * Cultural group, a group whose members share the same cultural identity * Ethnic group, a group whose members share the same ethnic iden ...

''G''. This means that, if an edge ''e'' in one direction has label ''g'' (a group element), then in the other direction it has label ''g''⁻¹. The label function ''φ'' therefore has the property that it is defined differently, but not independently, on the two different orientations, or directions, of an edge ''e''. The group ''G'' is called the gain group, ''φ'' is the gain function, and the value ''φ''(''e'') is the gain of ''e'' (in some indicated direction). A gain graph is a generalization of a

signed graph In the area of graph theory in mathematics, a signed graph is a graph in which each edge has a positive or negative sign. A signed graph is balanced if the product of edge signs around every cycle is positive. The name "signed graph" and the no ...

, where the gain group ''G'' has only two elements. See Zaslavsky (1989, 1991). A gain should not be confused with a weight on an edge, whose value is independent of the orientation of the edge.

Applications

Some reasons to be interested in gain graphs are their connections to network flow theory in

combinatorial optimization Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combi ...

, to

geometry Geometry (; ) is, with arithmetic, one of the oldest branches of mathematics. It is concerned with properties of space such as the distance, shape, size, and relative position of figures. A mathematician who works in the field of geometry is c ...

, and to

physics Physics is the natural science that studies matter, its fundamental constituents, its motion and behavior through space and time, and the related entities of energy and force. "Physical science is that department of knowledge which r ...

. * The mathematics of a network with gains, or

generalized network In graph theory, a flow network (also known as a transportation network) is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in operations res ...

, is connected with the frame matroid of the gain graph. * Suppose we have some

hyperplane In geometry, a hyperplane is a subspace whose dimension is one less than that of its ''ambient space''. For example, if a space is 3-dimensional then its hyperplanes are the 2-dimensional planes, while if the space is 2-dimensional, its hyper ...

s in ''R ⁿ'' given by equations of the form ''x_j'' = ''g x_i'' . The geometry of the hyperplanes can be treated by using the following gain graph: The vertex set is {1,2,...,''n''}. There is an edge ''ij'' with gain ''g'' (in the direction from ''i'' to ''j'') for each hyperplane with equation ''x_j = g x_i'' . These hyperplanes are treated through the frame matroid of the gain graph (Zaslavsky 2003). * Or, suppose we have hyperplanes given by equations of the form ''x_j'' = ''x_i'' + ''g''. The geometry of these hyperplanes can be treated by using the gain graph with the same vertex set and an edge ''ij'' with gain ''g'' (in the direction from ''i'' to ''j'') for each hyperplane with equation ''x_j'' = ''x_i'' + ''g''. These hyperplanes are studied via the lift matroid of the gain graph (Zaslavsky 2003). * Suppose the gain group has an

action Action may refer to: * Action (narrative), a literary mode * Action fiction, a type of genre fiction * Action game, a genre of video game Film * Action film, a genre of film * ''Action'' (1921 film), a film by John Ford * ''Action'' (1980 fil ...

on a set ''Q''. Assigning an element ''s_i'' of ''Q'' to each vertex gives a state of the gain graph. An edge is satisfied if, for each edge ''ij'' with gain ''g'' (in the direction from ''i'' to ''j''), the equation ''s_j'' = ''s_i g'' is satisfied; otherwise it is frustrated. A state is ''satisfied'' if every edge is satisfied. In physics this corresponds to a ground state (a state of lowest energy), if such a state exists. An important problem in physics, especially in the theory of

spin glass In condensed matter physics, a spin glass is a magnetic state characterized by randomness, besides cooperative behavior in freezing of spins at a temperature called 'freezing temperature' ''Tf''. In ferromagnetic solids, component atoms' magne ...

es, is to determine a state with the fewest frustrated edges.

Related concepts

Gain graphs used in

topological graph theory In mathematics, topological graph theory is a branch of graph theory. It studies the embedding of graphs in surfaces, spatial embeddings of graphs, and graphs as topological spaces. It also studies immersions of graphs. Embedding a graph in ...

as a means to construct

graph embedding In topological graph theory, an embedding (also spelled imbedding) of a Graph (discrete mathematics), graph G on a surface (mathematics), surface \Sigma is a representation of G on \Sigma in which points of \Sigma are associated with graph the ...

s in surfaces are known as "

voltage graph In graph theory, a voltage graph is a directed graph whose edges are labelled invertibly by elements of a group. It is formally identical to a gain graph, but it is generally used in topological graph theory as a concise way to specify another gra ...

s" (Gross 1974; Gross and Tucker 1977). The term "gain graph" is more usual in other contexts, e.g.,

biased graph {{Short description, Graph with a list of distinguished cycles In mathematics, a biased graph is a graph with a list of distinguished circles (edge sets of simple cycles), such that if two circles in the list are contained in a theta graph, then ...

theory and

matroid theory In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being in ...

. The term group-labelled graph has also been used, but it is ambiguous since "group labels" may be—and have been—treated as weights. Since much of the theory of gain graphs is a special case of that of biased graphs (and much of the theory of biased graphs is a generalization of that of gain graphs), the reader should refer to the article on

s for more information and examples.

References

*Jonathan L. Gross (1974), Voltage graphs. ''Discrete Mathematics'', Vol. 9, pp. 239–246. *J.L. Gross and T.W. Tucker (1977), Generating all graph coverings by permutation voltage assignments. ''Discrete Mathematics'', Vol. 18, pp. 273–283. *

Thomas Zaslavsky Thomas Zaslavsky (born 1945) is an American mathematician specializing in combinatorics. Zaslavsky's mother Claudia Zaslavsky was a high school mathematics teacher and an ethnomathematician in New York; his father Sam Zaslavsky (from Manhattan) ...

(1989), Biased graphs. I. Bias, balance, and gains. ''Journal of Combinatorial Theory, Series B'', Vol. 47, 32–52. *Thomas Zaslavsky (1991), Biased graphs. II. The three matroids. ''Journal of Combinatorial Theory, Series B'', Vol. 51, 46–72. *Thomas Zaslavsky (1999). A mathematical bibliography of signed and gain graphs and allied areas.
''Electronic Journal of Combinatorics'', Dynamic Surveys in Combinatorics, #DS8
*Thomas Zaslavsky (2003), Biased graphs IV: Geometrical realizations. ''Journal of Combinatorial Theory, Series B'', Vol. 89, no. 2, pp. 231–297. Matroid theory Extensions and generalizations of graphs